문서의 임의 삭제는 제재 대상으로, 문서를 삭제하려면 삭제 토론을 진행해야 합니다. 문서 보기문서 삭제토론 RSA 암호화 (문단 편집) === 키 만들기 === 1. 두 [[소수(수론)|소수]] [math( p , q )] 를 준비한다.[* 이들은 보통 굉장히 큰 홀수를 일단 랜덤하게 만든 다음, 소수를 얻을 때까지 2씩 더해 가며 찾는다. 소수의 분포가 그리 희박하진 않기에 가능한 방식이다. 참고로 해당 수가 소수인지 아닌지 판별하는 방법(primality test)이 다소 골때리는데, 이에 대해선 아래 내용 참고.] 1. [math( p - 1,\ q - 1 )]과 각각 [[서로소]]인 정수 [math(e)][* e는 지수를 의미하는 '''e'''xponent에서 딴 것이다. encryption에서 딴 게 아니다. 왜냐하면 암호화할 때 평문에 e제곱을 하기 때문이다. 공개키는 비교적 선택이 자유롭기에 보통 1의 비트가 2개인, 3(11,,2,,)이나 65537(10000000000000001,,2,,) 같은 소수를 쓴다.]를 준비한다. 1. [math(ed)]를 [math((p - 1)(q - 1))][* [[오일러 피 함수|[math(\phi(pq))]]]이다.]으로 나눈 나머지가 1이 되도록 하는 [math(d)][* d는 '''d'''ecryption에서 딴 것이다.]를 찾는다.[* 확장된 유클리드 호제법을 이용하면 금방 구할 수 있다. 다만 e가 (p - 1)(q - 1)와 서로소가 아니라면 이를 만족하는 d는 존재하지 않기 때문에 2번 과정이 필요하다.] 1. [math(N = pq)]를 계산한 후, [math(N)]과 [math(e)]를 공개한다. 이들이 바로 '''공개키'''이며, 상대방이 평서문[* 물론 A = 01, B = 02, ... , Z = 26 등의 방법으로 문장을 숫자 형태로 바꿔야 한다.]을 암호문으로 바꿀때 쓴다. 한편 [math(d)]는 숨겨두는데, 이 수가 바로 '''개인키'''이며, 공개키로 상대방이 만든 암호문을 해독할 때 쓴다. 1. 이제 [math(p, q, (p-1)(q-1))]는 필요 없거니와 있어 봐야 보안에 오히려 문제를 일으킬 수 있으니, 파기한다.[* 실제로는 공개키 암호화 표준에선 개인키가 {d,N} 혹은 {p, q, dP, dQ, qInv, (r_i, d_i, t_i)}로 표현된다. 후자의 값들은 연산 최적화를 위한 값들로 p,q도 포함된다.] N을 계수라 부르고 e를 지수라고 부르는데 e는 주로 65537(0x10001)을 사용한다. RSA의 키 사이즈를 말할 때 주로 N의 사이즈를 의미하며 사이즈가 2048일 경우라면 정수 N의 크기가 2^2047과 2^2048의 사이라는 의미이다. 한편 소수 [math(p)]와 [math(q)]를 구하는 과정은 여전히 완전한 방법이 없다고 봐야 한다. 일단 [[에라토스테네스의 체]]를 이용한 방식을 생각해 볼 수 있는데, [math(\sqrt{p})]보다 작은 소수들 모두로 나눠 봐야 알 수 있다는 점에서 이 방법은 현실적으로 불가능한 방법이다. 그래서 대신에 확률적으로 소수인지 아닌지를 판별하는 방법을 쓴다. 기본적으로 쓰는 방식이 아래에 소개할 [[페르마의 소정리]]를 근거로 한 것인데, 이 정리의 대우명제인 '임의의 정수 [math(a)]에 대해 [math(a^{p - 1})]를 [math(p)]로 나눈 나머지가 1이 아니면 [math(p)]는 소수가 아니다'라는 사실을 이용한 것이다. 이 방법을 쓰면 상당 확률로 소수를 걸러낼 수 있다고 한다. 하지만 물론 완전하진 않으며[* [[페르마의 소정리#s-3.2|카마이클 수]]라고 해서, 페르마의 소정리로는 소수임을 판정할 수 없는 유사 소수가 있다. 심지어 카마이클 수는 그 수가 무한하기 때문에 해당 수가 정말로 소수인지 판별하기 위해서는 소수와 유사 소수들을 모아놓은 집합에 대하여 여러가지 다른 소수 판정법으로 체로 걸러내야만 한다.] 이 때문에 다른 소수 판정법을 같이 쓰기도 한다.저장 버튼을 클릭하면 당신이 기여한 내용을 CC-BY-NC-SA 2.0 KR으로 배포하고,기여한 문서에 대한 하이퍼링크나 URL을 이용하여 저작자 표시를 하는 것으로 충분하다는 데 동의하는 것입니다.이 동의는 철회할 수 없습니다.캡챠저장미리보기